package datastructure.LRU;

/**
 * @Author ZhangCuirong
 * @Date 2025/7/31 16:19
 * @description:
 */
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class LRUCacheWithExpiration<K, V> {
    // 缓存节点，存储键、值、过期时间和前后指针
    static class Node<K, V> {
        K key;
        V value;
        long expireTime; // 过期时间戳(毫秒)，0表示永不过期
        Node<K, V> prev;
        Node<K, V> next;

        public Node(K key, V value, long expireTime) {
            this.key = key;
            this.value = value;
            this.expireTime = expireTime;
        }
    }

    private final int capacity; // 缓存最大容量
    private final Map<K, Node<K, V>> cache; // 哈希表用于快速查找
    private final Node<K, V> head; // 头节点(最近最少使用)
    private final Node<K, V> tail; // 尾节点(最近使用)

    // 构造函数，指定缓存容量
    public LRUCacheWithExpiration(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("容量必须为正数");
        }
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);

        // 初始化哨兵节点，避免空指针判断
        head = new Node<>(null, null, 0);
        tail = new Node<>(null, null, 0);
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 获取缓存中的值
     * @param key 键
     * @return 值，如果键不存在或已过期则返回null
     */
    public V get(K key) {
        Node<K, V> node = cache.get(key);
        if (node == null) {
            return null;
        }

        // 检查是否过期
        if (isExpired(node)) {
            removeNode(node);
            cache.remove(key);
            return null;
        }

        // 将节点移到尾部，表示最近使用
        moveToTail(node);
        return node.value;
    }

    /**
     * 向缓存中添加键值对
     * @param key 键
     * @param value 值
     * @param expireAfterMillis 过期时间(毫秒)，0表示永不过期
     */
    public void put(K key, V value, long expireAfterMillis) {
        if (expireAfterMillis < 0) {
            throw new IllegalArgumentException("过期时间不能为负数");
        }

        Node<K, V> node = cache.get(key);

        if (node != null) {
            // 键已存在，更新值和过期时间
            node.value = value;
            node.expireTime = expireAfterMillis > 0 ?
                    System.currentTimeMillis() + expireAfterMillis : 0;
            moveToTail(node);
            return;
        }

        // 检查缓存是否已满
        if (cache.size() >= capacity) {
            // 先清除所有过期节点
            cleanExpired();

            // 如果还是满的，移除最近最少使用的节点
            if (cache.size() >= capacity) {
                Node<K, V> leastUsed = head.next;
                cache.remove(leastUsed.key);
                removeNode(leastUsed);
            }
        }

        // 创建新节点并添加到缓存
        long expireTime = expireAfterMillis > 0 ?
                System.currentTimeMillis() + expireAfterMillis : 0;
        Node<K, V> newNode = new Node<>(key, value, expireTime);
        cache.put(key, newNode);
        addToTail(newNode);
    }

    /**
     * 移除指定键的缓存项
     * @param key 要移除的键
     * @return 被移除的值，如果键不存在则返回null
     */
    public V remove(K key) {
        Node<K, V> node = cache.get(key);
        if (node == null) {
            return null;
        }

        removeNode(node);
        cache.remove(key);
        return node.value;
    }

    /**
     * 检查节点是否过期
     */
    private boolean isExpired(Node<K, V> node) {
        // 过期时间为0表示永不过期
        return node.expireTime != 0 && System.currentTimeMillis() > node.expireTime;
    }

    /**
     * 清除所有过期的缓存项
     */
    public void cleanExpired() {
        long now = System.currentTimeMillis();
        // 使用迭代器避免ConcurrentModificationException
        for (Iterator<Node<K, V>> it = cache.values().iterator(); it.hasNext(); ) {
            Node<K, V> node = it.next();
            if (node.expireTime != 0 && now > node.expireTime) {
                removeNode(node);
                it.remove();
            }
        }
    }

    /**
     * 将节点移到尾部(表示最近使用)
     */
    private void moveToTail(Node<K, V> node) {
        removeNode(node);
        addToTail(node);
    }

    /**
     * 从链表中移除节点
     */
    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 将节点添加到尾部
     */
    private void addToTail(Node<K, V> node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }

    /**
     * 获取缓存当前大小
     */
    public int size() {
        return cache.size();
    }

    /**
     * 获取缓存容量
     */
    public int getCapacity() {
        return capacity;
    }

    // 测试方法
    public static void main(String[] args) throws InterruptedException {
        LRUCacheWithExpiration<String, Integer> cache = new LRUCacheWithExpiration<>(3);

        // 添加缓存项，设置不同的过期时间
        cache.put("a", 1, 1000);  // 1秒后过期
        cache.put("b", 2, 2000);  // 2秒后过期
        cache.put("c", 3, 3000);  // 3秒后过期

        System.out.println("获取a: " + cache.get("a"));  // 1
        System.out.println("获取b: " + cache.get("b"));  // 2

        // 添加第四个元素，会淘汰最近最少使用的c
        cache.put("d", 4, 0);     // 永不过期

        System.out.println("获取c: " + cache.get("c"));  // null，已被淘汰

        // 等待1.5秒，让a过期
        Thread.sleep(1500);
        System.out.println("1.5秒后获取a: " + cache.get("a"));  // null，已过期
        System.out.println("1.5秒后获取b: " + cache.get("b"));  // 2，尚未过期

        // 再等待1秒，让b过期
        Thread.sleep(1000);
        System.out.println("再1秒后获取b: " + cache.get("b"));  // null，已过期
        System.out.println("获取d: " + cache.get("d"));  // 4，永不过期
    }
}
